<!DOCTYPE HTML>
<html lang="en" >
    
    <head>
        
        <meta charset="UTF-8">
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <title>快速排序 | python 数据结构与算法</title>
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="">
        <meta name="generator" content="GitBook 2.6.7">
        
        
        <meta name="HandheldFriendly" content="true"/>
        <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
        <meta name="apple-mobile-web-app-capable" content="yes">
        <meta name="apple-mobile-web-app-status-bar-style" content="black">
        <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../gitbook/images/apple-touch-icon-precomposed-152.png">
        <link rel="shortcut icon" href="../gitbook/images/favicon.ico" type="image/x-icon">
        
    <link rel="stylesheet" href="../gitbook/style.css">
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-highlight/website.css">
        
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-search/search.css">
        
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-fontsettings/website.css">
        
    
    

        
    
    
    <link rel="next" href="../算法的介绍/字典序算法.html" />
    
    
    <link rel="prev" href="../六大排序/六大基本排序.html" />
    

        
    </head>
    <body>
        
        
    <div class="book"
        data-level="3.2"
        data-chapter-title="快速排序"
        data-filepath="六大排序/快速排序.md"
        data-basepath=".."
        data-revision="Mon Jun 10 2019 17:10:15 GMT+0800 (中国标准时间)"
        data-innerlanguage="">
    

<div class="book-summary">
    <nav role="navigation">
        <ul class="summary">
            
            
            
            

            

            
    
        <li class="chapter " data-level="0" data-path="index.html">
            
                
                    <a href="../index.html">
                
                        <i class="fa fa-check"></i>
                        
                        python数据结构与算法
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1" >
            
            <span><b>1.</b> 剑指offer</span>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.1" data-path="剑指offer/补码.html">
            
                
                    <a href="../剑指offer/补码.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.1.</b>
                        
                        补码
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="剑指offer/剑指offer1-24题.html">
            
                
                    <a href="../剑指offer/剑指offer1-24题.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.2.</b>
                        
                        剑指offer1-24题
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="剑指offer/剑指offer25-43题.html">
            
                
                    <a href="../剑指offer/剑指offer25-43题.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.3.</b>
                        
                        剑指offer25-43题
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="2" data-path="树的实现/树的定义.html">
            
                
                    <a href="../树的实现/树的定义.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.</b>
                        
                        各种树
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="2.1" data-path="树的实现/B-树.html">
            
                
                    <a href="../树的实现/B-树.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.1.</b>
                        
                        B-树
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="2.2" data-path="树的实现/B+树.html">
            
                
                    <a href="../树的实现/B+树.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.2.</b>
                        
                        B+树
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="2.3" data-path="树的实现/红黑树.html">
            
                
                    <a href="../树的实现/红黑树.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.3.</b>
                        
                        红黑树
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="3" >
            
            <span><b>3.</b> 六大排序</span>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="3.1" data-path="六大排序/六大基本排序.html">
            
                
                    <a href="../六大排序/六大基本排序.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>3.1.</b>
                        
                        六大基本排序
                    </a>
            
            
        </li>
    
        <li class="chapter active" data-level="3.2" data-path="六大排序/快速排序.html">
            
                
                    <a href="../六大排序/快速排序.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>3.2.</b>
                        
                        快速排序
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="4" >
            
            <span><b>4.</b> 算法的介绍</span>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="4.1" data-path="算法的介绍/字典序算法.html">
            
                
                    <a href="../算法的介绍/字典序算法.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>4.1.</b>
                        
                        字典序算法
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="4.2" data-path="算法的介绍/布隆算法.html">
            
                
                    <a href="../算法的介绍/布隆算法.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>4.2.</b>
                        
                        布隆算法
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    


            
            <li class="divider"></li>
            <li>
                <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
                    Published with GitBook
                </a>
            </li>
            
        </ul>
    </nav>
</div>

    <div class="book-body">
        <div class="body-inner">
            <div class="book-header" role="navigation">
    <!-- Actions Left -->
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href="../" >python 数据结构与算法</a>
    </h1>
</div>

            <div class="page-wrapper" tabindex="-1" role="main">
                <div class="page-inner">
                
                
                    <section class="normal" id="section-">
                    
                        <p>&#x5FEB;&#x901F;&#x6392;&#x5E8F;</p>
<p>&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x662F;&#x624D;&#x80FD;&#x591F;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x6F14;&#x53D8;&#x800C;&#x6765;&#x7684;&#x7B97;&#x6CD5;&#xFF0C;&#x4F46;&#x662F;&#x6BD4;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x8981;&#x9AD8;&#x6548;&#x7684;&#x591A;&#xFF0C;&#x6240;&#x4EE5;&#x53EB;&#x505A;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x3002;</p>
<p>&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x4E4B;&#x6240;&#x4EE5;&#x5FEB;&#x901F;&#xFF0C;&#x662F;&#x56E0;&#x4E3A;&#x5B83;&#x4F7F;&#x7528;&#x4E86;&#x3010;&#x5206;&#x6CBB;&#x6CD5;&#x3011;</p>
<p>&#x540C;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x4E00;&#x6837;&#xFF0C;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x4E5F;&#x5C5E;&#x4E8E;<strong>&#x4EA4;&#x6362;&#x6392;&#x5E8F;</strong>&#xFF0C;&#x901A;&#x8FC7;&#x5143;&#x7D20;&#x4E4B;&#x95F4;&#x7684;&#x6BD4;&#x8F83;&#x548C;&#x4EA4;&#x6362;&#x4F4D;&#x7F6E;&#x6765;&#x8FBE;&#x5230;&#x6392;&#x5E8F;&#x7684;&#x76EE;&#x7684;&#x3002;</p>
<p>&#x4E0D;&#x540C;&#x7684;&#x662F;&#xFF0C;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x5728;&#x6BCF;&#x4E00;&#x8F6E;&#x53EA;&#x628A;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x5192;&#x6CE1;&#x5230;&#x6570;&#x5217;&#x7684;&#x4E00;&#x7AEF;&#xFF0C;&#x800C;&#x5FEB;&#x901F;&#x6392;&#x5E8F;<strong>&#x5728;&#x6BCF;&#x4E00;&#x8F6E;&#x6311;&#x9009;&#x4E00;&#x4E2A;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#xFF0C;&#x5E76;&#x8BA9;&#x5176;&#x4ED6;&#x6BD4;&#x5B83;&#x5927;&#x7684;&#x5143;&#x7D20;&#x79FB;&#x52A8;&#x5230;&#x6570;&#x5217;&#x4E00;&#x8FB9;&#xFF0C;&#x6BD4;&#x5B83;&#x5C0F;&#x7684;&#x5143;&#x7D20;&#x79FB;&#x52A8;&#x5230;&#x6570;&#x5217;&#x7684;&#x53E6;&#x4E00;&#x8FB9;&#xFF0C;&#x4ECE;&#x800C;&#x628A;&#x6570;&#x5217;&#x62C6;&#x89E3;&#x6210;&#x4E86;&#x4E24;&#x4E2A;&#x90E8;&#x5206;&#x3002;</strong></p>
<p><img src="images/&#x5FEB;&#x901F;&#x6392;&#x5E8F;.png" alt=""></p>
<p>&#x8FD9;&#x79CD;&#x601D;&#x8DEF;&#x5C31;&#x53EB;&#x505A;<strong>&#x5206;&#x6CBB;&#x6CD5;</strong>&#x3002;</p>
<p>&#x6BCF;&#x6B21;&#x628A;&#x6570;&#x5217;&#x5206;&#x6210;&#x4E24;&#x90E8;&#x5206;&#xFF0C;&#x7A76;&#x7ADF;&#x6709;&#x4EC0;&#x4E48;&#x597D;&#x5904;&#x5462;&#xFF1F;</p>
<p>&#x5047;&#x5982;&#x7ED9;&#x5B9A;8&#x4E2A;&#x5143;&#x7D20;&#x7684;&#x6570;&#x5217;&#xFF0C;&#x4E00;&#x822C;&#x60C5;&#x51B5;&#x4E0B;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x9700;&#x8981;&#x6BD4;&#x8F83;8&#x8F6E;&#xFF0C;&#x6BCF;&#x8F6E;&#x628A;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x79FB;&#x52A8;&#x5230;&#x6570;&#x5217;&#x4E00;&#x7AEF;&#xFF0C;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F;O&#xFF08;n^2&#xFF09;&#x3002;</p>
<p><img src="images/&#x5FEB;&#x901F;&#x6392;&#x5E8F;2.png" alt=""></p>
<p>&#x5982;&#x56FE;&#x6240;&#x793A;&#xFF0C;&#x5728;&#x5206;&#x6CBB;&#x6CD5;&#x7684;&#x601D;&#x60F3;&#x4E0B;&#xFF0C;&#x539F;&#x6570;&#x5217;&#x5728;&#x6BCF;&#x4E00;&#x8F6E;&#x88AB;&#x62C6;&#x5206;&#x6210;&#x4E24;&#x90E8;&#x5206;&#xFF0C;&#x6BCF;&#x4E00;&#x90E8;&#x5206;&#x5728;&#x4E0B;&#x4E00;&#x8F6E;&#x53C8;&#x5206;&#x522B;&#x88AB;&#x62C6;&#x5206;&#x6210;&#x4E24;&#x90E8;&#x5206;&#xFF0C;&#x76F4;&#x5230;&#x4E0D;&#x53EF;&#x518D;&#x5206;&#x4E3A;&#x6B62;&#x3002;</p>
<p>&#x8FD9;&#x6837;&#x4E00;&#x5171;&#x9700;&#x8981;&#x591A;&#x5C11;&#x8F6E;&#x5462;&#xFF1F;&#x5E73;&#x5747;&#x60C5;&#x51B5;&#x4E0B;&#x9700;&#x8981;logn&#x8F6E;&#xFF0C;&#x56E0;&#x6B64;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x7684;&#x5E73;&#x5747;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F; <strong>O&#xFF08;nlogn&#xFF09;</strong>&#x3002;</p>
<p>&#x57FA;&#x51C6;&#x5143;&#x7D20;&#x7684;&#x9009;&#x62E9;&#xFF0C;&#x4EE5;&#x53CA;&#x5143;&#x7D20;&#x7684;&#x79FB;&#x52A8;&#xFF0C;&#x90FD;&#x662F;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x7684;&#x6838;&#x5FC3;&#x95EE;&#x9898;&#x3002;</p>
<p><strong>&#x57FA;&#x51C6;&#x5143;&#x7D20;&#x7684;&#x9009;&#x62E9;</strong></p>
<p>&#x57FA;&#x51C6;&#x5143;&#x7D20;&#xFF0C;&#x82F1;&#x6587;pivot&#xFF0C;&#x7528;&#x4E8E;&#x5728;&#x5206;&#x6CBB;&#x8FC7;&#x7A0B;&#x4E2D;&#x4EE5;&#x6B64;&#x4E3A;&#x4E2D;&#x5FC3;&#xFF0C;&#x628A;&#x5176;&#x4ED6;&#x5143;&#x7D20;&#x79FB;&#x52A8;&#x5230;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#x7684;&#x5DE6;&#x53F3;&#x4E24;&#x8FB9;&#x3002;</p>
<p>&#x90A3;&#x4E48;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#x5982;&#x4F55;&#x9009;&#x62E9;&#x5462;&#xFF1F;</p>
<p>&#x6700;&#x7B80;&#x5355;&#x7684;&#x65B9;&#x5F0F;&#x662F;&#x9009;&#x62E9;&#x6570;&#x5217;&#x7684;&#x7B2C;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#xFF1A;</p>
<p>&#x6700;&#x53F3;&#x8FB9;&#x6216;&#x8005;&#x6700;&#x5DE6;&#x8FB9;&#x7684;&#x5143;&#x7D20;&#x3002;</p>
<p>&#x8FD9;&#x79CD;&#x9009;&#x62E9;&#x5728;&#x7EDD;&#x5927;&#x591A;&#x6570;&#x60C5;&#x51B5;&#x662F;&#x6CA1;&#x6709;&#x95EE;&#x9898;&#x7684;&#x3002;&#x4F46;&#x662F;&#xFF0C;&#x5047;&#x5982;&#x6709;&#x4E00;&#x4E2A;&#x539F;&#x672C;&#x9006;&#x5E8F;&#x7684;&#x6570;&#x5217;&#xFF0C;&#x671F;&#x671B;&#x6392;&#x5E8F;&#x6210;&#x987A;&#x5E8F;&#x6570;&#x5217;&#xFF0C;&#x90A3;&#x4E48;&#x4F1A;&#x51FA;&#x73B0;&#x4EC0;&#x4E48;&#x60C5;&#x51B5;&#x5462;&#xFF1F;</p>
<p><img src="images/&#x5FEB;&#x901F;&#x6392;&#x5E8F;3.png" alt=""></p>
<p>&#x6574;&#x4E2A;&#x6570;&#x5217;&#x5E76;&#x6CA1;&#x6709;&#x88AB;&#x5206;&#x6210;&#x4E00;&#x534A;&#x4E00;&#x534A;&#xFF0C;&#x6BCF;&#x4E00;&#x8F6E;&#x4EC5;&#x4EC5;&#x786E;&#x5B9A;&#x4E86;&#x57FA;&#x51C6; &#x5143;&#x7D20;&#x7684;&#x4F4D;&#x7F6E;&#xFF0C;</p>
<p>&#x8FD9;&#x79CD;&#x60C5;&#x51B5;&#x4E0B;&#x6570;&#x5217;&#x7B2C;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x8981;&#x4E48;&#x662F;&#x6700;&#x5C0F;&#x503C;&#xFF0C;&#x8981;&#x4E48;&#x662F;&#x6700;&#x5927;&#x503C;&#xFF0C;&#x6839;&#x672C;&#x65E0;&#x6CD5;&#x53D1;&#x6325;&#x5206;&#x6CBB;&#x6CD5;&#x7684;&#x4F18;&#x52BF;&#x3002;</p>
<p>&#x5728;&#x8FD9;&#x79CD;&#x6781;&#x7AEF;&#x60C5;&#x51B5;&#x4E0B;&#xFF0C;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x9700;&#x8981;&#x8FDB;&#x884C;N&#x8F6E;&#xFF0C;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x9000;&#x5316;&#x6210;&#x4E86;O&#xFF08;N&#x2026;&#x2026;2&#xFF09;</p>
<p>&#x4E3A;&#x4E86;&#x907F;&#x514D;&#x4E0A;&#x9762;&#x7684;&#x60C5;&#x51B5;&#x53D1;&#x751F;&#xFF0C;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x4E0D;&#x9009;&#x62E9;&#x6570;&#x5217;&#x7684;&#x7B2C;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#xFF0C;&#x800C;&#x662F;&#x968F;&#x673A;&#x9009;&#x62E9;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x4F5C;&#x4E3A;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#xFF0C;</p>
<p>&#x8FD9;&#x6837;&#x4E00;&#x6765;&#xFF0C;&#x5373;&#x4F7F;&#x5728;&#x6570;&#x5217;&#x5B8C;&#x5168;&#x9006;&#x5E8F;&#x7684;&#x60C5;&#x51B5;&#x4E0B;&#xFF0C;&#x4E5F;&#x53EF;&#x4EE5;&#x6709;&#x6548;&#x5730;&#x5C06;&#x6570;&#x5217;&#x5206;&#x6210;&#x4E24;&#x90E8;&#x5206;&#x3002;</p>
<p>&#x5F53;&#x7136;&#xFF0C;&#x5373;&#x4F7F;&#x662F;&#x968F;&#x673A;&#x9009;&#x62E9;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#xFF0C;&#x6BCF;&#x4E00;&#x6B21;&#x4E5F;&#x6709;&#x6781;&#x5C0F;&#x7684;&#x51E0;&#x7387;&#x9009;&#x5230;&#x6570;&#x5217;&#x7684;&#x6700;&#x5927;&#x503C;&#x6216;&#x6700;&#x5C0F;&#x503C;&#xFF0C;&#x540C;&#x6837;&#x4F1A;&#x5F71;&#x54CD;&#x5230;&#x5206;&#x6CBB;&#x7684;&#x6548;&#x679C;&#x3002;</p>
<p>&#x6240;&#x4EE5;&#xFF0C;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x7684;&#x5E73;&#x5747;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F; <strong>O&#xFF08;n**</strong>logn&#xFF09;&#xFF0C;<strong>&#x6700;&#x574F;&#x60C5;&#x51B5;&#x4E0B;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F; </strong>O&#xFF08;n^2&#xFF09;**&#x3002;</p>
<h4 id="&#x4E00;&#x4E0B;&#x5C31;&#x662F;&#x5206;&#x6CBB;&#x6CD5;&#x7684;&#x4EE3;&#x7801;&#x7684;&#x5B9E;&#x73B0;&#xFF1A;">&#x4E00;&#x4E0B;&#x5C31;&#x662F;&#x5206;&#x6CBB;&#x6CD5;&#x7684;&#x4EE3;&#x7801;&#x7684;&#x5B9E;&#x73B0;&#xFF1A;</h4>
<hr>
<h3 id="&#x4EE3;&#x7801;&#x7684;&#x5B9E;&#x73B0;&#xFF1A;">&#x4EE3;&#x7801;&#x7684;&#x5B9E;&#x73B0;&#xFF1A;</h3>
<pre><code class="lang-python"><span class="hljs-comment">#&#x5FEB;&#x6392;&#x7684;&#x4E3B;&#x51FD;&#x6570;&#xFF0C;&#x4F20;&#x5165;&#x53C2;&#x6570;&#x4E3A;&#x4E00;&#x4E2A;&#x5217;&#x8868;&#xFF0C;&#x5DE6;&#x53F3;&#x4E24;&#x7AEF;&#x7684;&#x4E0B;&#x6807;</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">QuickSort</span><span class="hljs-params">(array,leftIndex=<span class="hljs-number">0</span>,rightIndex=None)</span>:</span>
    <span class="hljs-comment">#&#x6570;&#x7EC4;&#x7684;&#x957F;&#x5EA6;</span>
    arrayLen = len(array)
    <span class="hljs-comment">#&#x957F;&#x5EA6;&#x4E3A;1 &#x7684;&#x8BDD; &#x6216;&#x8005; &#x7A7A; &#x7684;&#x8BDD; &#x76F4;&#x63A5;&#x8FD4;&#x56DE; &#x6570;&#x7EC4;</span>
    <span class="hljs-keyword">if</span> arrayLen &lt;= <span class="hljs-number">1</span>:
        <span class="hljs-keyword">return</span> array
    <span class="hljs-comment">#&#x7A0B;&#x5E8F;&#x4E00;&#x5F00;&#x59CB; &#x5982;&#x679C;&#x6CA1;&#x6709;&#x7ED9;&#x4E00;&#x4E2A;&#x6700;&#x53F3;&#x8FB9;&#x7684;&#x7D22;&#x5F15;&#x503C;&#x5BFC;&#x5165;&#x8BDD;&#xFF0C;&#x90A3;&#x4E48;&#x6211;&#x4EEC;&#x5C31;&#x7ED9;&#x5B83; &#x8D4B;&#x503C;&#x4E00;&#x4E2A; &#x5C31;&#x662F;&#x6570;&#x7EC4;&#x7684;&#x6700;&#x53F3;&#x8FB9;&#x7684; &#x90A3;&#x4E2A;&#x7D22;&#x5F15;&#x503C;&#x3002;</span>
    <span class="hljs-keyword">if</span> rightIndex == <span class="hljs-keyword">None</span>:
        rightIndex = arrayLen - <span class="hljs-number">1</span>
    <span class="hljs-comment"># &#x4FDD;&#x62A4;&#x6761;&#x4EF6;&#xFF0C;&#x53EA;&#x6709;&#x6EE1;&#x8DB3;  &#x5DE6;&#x8FB9;&#x7D22;&#x5F15;&#x5C0F;&#x4E8E;&#x53F3;&#x8FB9;&#x7D22;&#x5F15;&#x7684;&#x65F6;&#x5019; &#x518D;&#x5F00;&#x59CB;&#x6392;&#x5E8F;</span>
    <span class="hljs-keyword">if</span> leftIndex &lt; rightIndex:
        <span class="hljs-comment">#&#x627E;&#x5230; &#x57FA;&#x51C6;&#x7684; &#x7D22;&#x5F15;&#x503C; &#x4F20;&#x5165;&#x53C2;&#x6570;&#xFF0C;&#x901A;&#x8FC7;Partitions&#x51FD;&#x6570;&#xFF0C;&#x83B7;&#x53D6;k&#x4E0B;&#x6807;&#x503C;</span>
        pivot = partition(array,leftIndex,rightIndex)
        <span class="hljs-comment">#&#x9012;&#x5F52;&#x524D;&#x540E;&#x534A;&#x533A; &#x5BF9;&#x57FA;&#x51C6;&#x524D;&#x9762;&#x4E0D;&#x90E8;&#x5206;&#x7EE7;&#x7EED;&#x5FEB;&#x6392;</span>
        QuickSort(array,leftIndex,pivot - <span class="hljs-number">1</span>)
        <span class="hljs-comment">#&#x5BF9;&#x57FA;&#x51C6;&#x540E;&#x534A;&#x79EF;&#x5206;&#x7EE7;&#x7EED;&#x5FEB;&#x6392;</span>
        QuickSort(array,pivot + <span class="hljs-number">1</span>,rightIndex)
</code></pre>
<hr>
<h3 id="&#x5143;&#x7D20;&#x7684;&#x79FB;&#x52A8;">&#x5143;&#x7D20;&#x7684;&#x79FB;&#x52A8;</h3>
<p>&#x9009;&#x5B9A;&#x4E86;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#x4EE5;&#x540E;&#xFF0C;&#x6211;&#x4EEC;&#x8981;&#x505A;&#x7684;&#x5C31;&#x662F;&#x628A;&#x5176;&#x4ED6;&#x5143;&#x7D20;&#x5F53;&#x4E2D;&#x5C0F;&#x4E8E;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#x7684;&#x90FD;&#x79FB;&#x52A8;&#x5230;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#x4E00;&#x8FB9;&#xFF0C;&#x5927;&#x4E8E;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#x7684;&#x90FD;&#x79FB;&#x52A8;&#x5230;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#x53E6;&#x4E00;&#x8FB9;&#x3002;       </p>
<h4 id="1&#x4EA4;&#x6362;&#x6307;&#x9488;&#x6CD5;&#xFF1A;">1.&#x4EA4;&#x6362;&#x6307;&#x9488;&#x6CD5;&#xFF1A;</h4>
<p>&#x4F55;&#x8C13;&#x6307;&#x9488;&#x4EA4;&#x6362;&#x6CD5;&#xFF1F;&#x6211;&#x4EEC;&#x6765;&#x770B;&#x4E00;&#x770B;&#x8BE6;&#x7EC6;&#x8FC7;&#x7A0B;&#x3002;</p>
<p>&#x7ED9;&#x5B9A;&#x539F;&#x59CB;&#x6570;&#x5217;&#x5982;&#x4E0B;&#xFF0C;&#x8981;&#x6C42;&#x4ECE;&#x5C0F;&#x5230;&#x5927;&#x6392;&#x5E8F;&#xFF1A;</p>
<p><img src="images/1.png" alt=""></p>
<p>&#x5F00;&#x5C40;&#x548C;&#x6316;&#x5751;&#x6CD5;&#x76F8;&#x4F3C;&#xFF0C;&#x6211;&#x4EEC;&#x9996;&#x5148;&#x9009;&#x5B9A;&#x57FA;&#x51C6;&#x5143;&#x7D20;Pivot&#xFF0C;&#x5E76;&#x4E14;&#x8BBE;&#x7F6E;&#x4E24;&#x4E2A;&#x6307;&#x9488;left&#x548C;right&#xFF0C;&#x6307;&#x5411;&#x6570;&#x5217;&#x7684;&#x6700;&#x5DE6;&#x548C;&#x6700;&#x53F3;&#x4E24;&#x4E2A;&#x5143;&#x7D20;&#xFF1A;</p>
<p><img src="images/2.png" alt=""></p>
<p>&#x63A5;&#x4E0B;&#x6765;&#x662F;<strong>&#x7B2C;&#x4E00;&#x6B21;&#x5FAA;&#x73AF;</strong>&#xFF0C;&#x4ECE;right&#x6307;&#x9488;&#x5F00;&#x59CB;&#xFF0C;&#x628A;&#x6307;&#x9488;&#x6240;&#x6307;&#x5411;&#x7684;&#x5143;&#x7D20;&#x548C;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#x505A;&#x6BD4;&#x8F83;&#x3002;&#x5982;&#x679C;<strong>&#x5927;&#x4E8E;&#x7B49;&#x4E8E;</strong>pivot&#xFF0C;&#x5219;&#x6307;&#x9488;&#x5411;<strong>&#x5DE6;</strong>&#x79FB;&#x52A8;&#xFF1B;&#x5982;&#x679C;<strong>&#x5C0F;&#x4E8E;</strong>pivot&#xFF0C;&#x5219;right&#x6307;&#x9488;&#x505C;&#x6B62;&#x79FB;&#x52A8;&#xFF0C;&#x5207;&#x6362;&#x5230;<strong>left</strong>&#x6307;&#x9488;&#x3002;</p>
<p>&#x5728;&#x5F53;&#x524D;&#x6570;&#x5217;&#x4E2D;&#xFF0C;1&lt;4&#xFF0C;&#x6240;&#x4EE5;right&#x76F4;&#x63A5;&#x505C;&#x6B62;&#x79FB;&#x52A8;&#xFF0C;&#x6362;&#x5230;left&#x6307;&#x9488;&#xFF0C;&#x8FDB;&#x884C;&#x4E0B;&#x4E00;&#x6B65;&#x884C;&#x52A8;&#x3002;</p>
<p>&#x8F6E;&#x5230;left&#x6307;&#x9488;&#x884C;&#x52A8;&#xFF0C;&#x628A;&#x6307;&#x9488;&#x6240;&#x6307;&#x5411;&#x7684;&#x5143;&#x7D20;&#x548C;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#x505A;&#x6BD4;&#x8F83;&#x3002;&#x5982;&#x679C;<strong>&#x5C0F;&#x4E8E;&#x7B49;&#x4E8E;</strong>pivot&#xFF0C;&#x5219;&#x6307;&#x9488;&#x5411;<strong>&#x53F3;</strong>&#x79FB;&#x52A8;&#xFF1B;&#x5982;&#x679C;<strong>&#x5927;&#x4E8E;</strong>pivot&#xFF0C;&#x5219;left&#x6307;&#x9488;&#x505C;&#x6B62;&#x79FB;&#x52A8;&#x3002;</p>
<p>&#x7531;&#x4E8E;left&#x4E00;&#x5F00;&#x59CB;&#x6307;&#x5411;&#x7684;&#x662F;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#xFF0C;&#x5224;&#x65AD;&#x80AF;&#x5B9A;&#x76F8;&#x7B49;&#xFF0C;&#x6240;&#x4EE5;left&#x53F3;&#x79FB;&#x4E00;&#x4F4D;&#x3002;</p>
<p><img src="images/11.png" alt=""></p>
<p>&#x7531;&#x4E8E;7 &gt; 4&#xFF0C;left&#x6307;&#x9488;&#x5728;&#x5143;&#x7D20;7&#x7684;&#x4F4D;&#x7F6E;&#x505C;&#x4E0B;&#x3002;&#x8FD9;&#x65F6;&#x5019;&#xFF0C;&#x6211;&#x4EEC;&#x8BA9;<strong>left&#x548C;right&#x6307;&#x5411;&#x7684;&#x5143;&#x7D20;&#x8FDB;&#x884C;&#x4EA4;&#x6362;</strong>&#x3002;</p>
<p><img src="images/12.png" alt=""></p>
<p>&#x63A5;&#x4E0B;&#x6765;&#xFF0C;&#x6211;&#x4EEC;&#x8FDB;&#x5165;<strong>&#x7B2C;&#x4E8C;&#x6B21;&#x5FAA;&#x73AF;</strong>&#xFF0C;&#x91CD;&#x65B0;&#x5207;&#x6362;&#x5230;right&#x5411;&#x5DE6;&#x79FB;&#x52A8;&#x3002;right&#x5148;&#x79FB;&#x52A8;&#x5230;8&#xFF0C;8&gt;4&#xFF0C;&#x7EE7;&#x7EED;&#x5DE6;&#x79FB;&#x3002;&#x7531;&#x4E8E;2&lt;4&#xFF0C;&#x505C;&#x6B62;&#x5728;2&#x7684;&#x4F4D;&#x7F6E;&#x3002;</p>
<p><img src="images/13.png" alt=""></p>
<p>&#x5207;&#x6362;&#x5230;left&#xFF0C;6&gt;4&#xFF0C;&#x505C;&#x6B62;&#x5728;6&#x7684;&#x4F4D;&#x7F6E;&#x3002;</p>
<p><img src="images/14.png" alt=""></p>
<p>&#x5143;&#x7D20;6&#x548C;2&#x4EA4;&#x6362;&#x3002;</p>
<p><img src="images/15.png" alt=""></p>
<p>&#x8FDB;&#x5165;<strong>&#x7B2C;&#x4E09;&#x6B21;&#x5FAA;&#x73AF;</strong>&#xFF0C;right&#x79FB;&#x52A8;&#x5230;&#x5143;&#x7D20;3&#x505C;&#x6B62;&#xFF0C;left&#x79FB;&#x52A8;&#x5230;&#x5143;&#x7D20;5&#x505C;&#x6B62;&#x3002;</p>
<p><img src="images/16.png" alt=""></p>
<p>&#x5143;&#x7D20;5&#x548C;3&#x4EA4;&#x6362;&#x3002;</p>
<p><img src="images/17.png" alt=""></p>
<p>&#x8FDB;&#x5165;<strong>&#x7B2C;&#x56DB;&#x6B21;&#x5FAA;&#x73AF;</strong>&#xFF0C;right&#x79FB;&#x52A8;&#x5230;&#x5143;&#x7D20;3&#x505C;&#x6B62;&#xFF0C;&#x8FD9;&#x65F6;&#x5019;&#x8BF7;&#x6CE8;&#x610F;&#xFF0C;left&#x548C;right&#x6307;&#x9488;&#x5DF2;&#x7ECF;&#x91CD;&#x5408;&#x5728;&#x4E86;&#x4E00;&#x8D77;&#x3002;</p>
<p><img src="images/18.png" alt=""></p>
<p>&#x5F53;left&#x548C;right&#x6307;&#x9488;&#x91CD;&#x5408;&#x4E4B;&#x65F6;&#xFF0C;&#x6211;&#x4EEC;&#x8BA9;pivot&#x5143;&#x7D20;&#x548C;left&#x4E0E;right&#x91CD;&#x5408;&#x70B9;&#x7684;&#x5143;&#x7D20;&#x8FDB;&#x884C;&#x4EA4;&#x6362;&#x3002;&#x6B64;&#x65F6;&#x6570;&#x5217;&#x5DE6;&#x8FB9;&#x7684;&#x5143;&#x7D20;&#x90FD;&#x5C0F;&#x4E8E;4&#xFF0C;&#x6570;&#x5217;&#x53F3;&#x8FB9;&#x7684;&#x5143;&#x7D20;&#x90FD;&#x5927;&#x4E8E;4&#xFF0C;&#x8FD9;&#x4E00;&#x8F6E;&#x4EA4;&#x6362;&#x7EC8;&#x544A;&#x7ED3;&#x675F;&#x3002;</p>
<p><img src="images/19.png" alt=""></p>
<h4 id="&#x4EE5;&#x4E0B;&#x4E3A;&#x4EA4;&#x6362;&#x6307;&#x9488;&#x5B9E;&#x73B0;&#x7684;partition&#x7684;&#x4EE3;&#x7801;&#xFF1A;">&#x4EE5;&#x4E0B;&#x4E3A;&#x4EA4;&#x6362;&#x6307;&#x9488;&#x5B9E;&#x73B0;&#x7684;partition&#x7684;&#x4EE3;&#x7801;&#xFF1A;</h4>
<pre><code class="lang-python"><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">partition</span><span class="hljs-params">(array,leftIndex,rightIndex)</span>:</span>

    pivotValue = array[rightIndex]

    <span class="hljs-comment">#&#x5C06;&#x6700;&#x5DE6;&#x4FA7;&#x7684; &#x7D22;&#x5F15;&#x503C; &#x7ED9; i</span>

    i  = leftIndex

    <span class="hljs-comment">#&#x5C06;&#x6700;&#x53F3;&#x4FA7;&#x7684; &#x7D22;&#x5F15;&#x7684;&#x524D;&#x4E00;&#x4E2A; &#x7ED9;j</span>

    j = rightIndex -<span class="hljs-number">1</span>

    <span class="hljs-comment">#&#x5F53;left&#x4E0B;&#x6807;&#xFF0C;&#x5C0F;&#x4E8E;right&#x4E0B;&#x6807;&#x7684;&#x60C5;&#x51B5;&#x4E0B;&#xFF0C;&#x6B64;&#x65F6;&#x5224;&#x65AD;&#x4E8C;&#x8005;&#x79FB;&#x52A8;&#x662F;&#x5426;&#x76F8;&#x4EA4;&#xFF0C;&#x82E5;&#x672A;&#x76F8;&#x4EA4;&#xFF0C;&#x5219;&#x4E00;&#x76F4;&#x5FAA;&#x73AF;</span>

    <span class="hljs-keyword">while</span> i &lt; j:

        <span class="hljs-comment"># &#x5F53;left&#x5BF9;&#x5E94;&#x7684;&#x503C;&#x5927;&#x4E8E;&#x951A;&#x70B9; &#x57FA;&#x51C6;&#x70B9; &#x53C2;&#x8003;&#x503C;&#xFF0C;&#x5C31;&#x4E00;&#x76F4;&#x5411;&#x5DE6;&#x79FB;&#x52A8;</span>

        <span class="hljs-keyword">while</span> j &gt; leftIndex <span class="hljs-keyword">and</span> array[j] &gt; pivotValue:

            j -= <span class="hljs-number">1</span>

        <span class="hljs-comment">#&#x5F53;left&#x5BF9;&#x5E94;&#x7684;&#x503C;&#x5C0F;&#x4E8E;&#x57FA;&#x51C6;&#x70B9;&#x53C2;&#x8003;&#x503C;&#xFF0C;&#x5C31;&#x4E00;&#x76F4;&#x5411;&#x53F3;&#x79FB;&#x52A8;</span>

        <span class="hljs-keyword">while</span> i &lt; rightIndex <span class="hljs-keyword">and</span> array[i] &lt;= pivotValue:

            i += <span class="hljs-number">1</span>

        <span class="hljs-comment">#&#x82E5;&#x79FB;&#x52A8;&#x5B8C;&#xFF0C;&#x4E8C;&#x8005;&#x4ECD;&#x672A;&#x76F8;&#x9047;&#x5219;&#x4EA4;&#x6362;&#x4E0B;&#x6807;&#x5BF9;&#x5E94;&#x7684;&#x503C;</span>

        <span class="hljs-keyword">if</span> i &lt; j:

            array[j],array[i] = array[i],array[j]

            i+=<span class="hljs-number">1</span>

            j-=<span class="hljs-number">1</span>

    <span class="hljs-comment">#&#x82E5;&#x79FB;&#x52A8;&#x5B8C;&#xFF0C;&#x5DF2;&#x7ECF;&#x76F8;&#x9047;&#xFF0C;&#x5219;&#x4EA4;&#x6362;right&#x5BF9;&#x5E94;&#x7684;&#x503C;&#x548C;&#x53C2;&#x8003;&#x503C;</span>

    array[i],array[rightIndex] = array[rightIndex],array[i]

    <span class="hljs-comment"># &#x8FD4;&#x56DE; &#x4E00;&#x4E2A; &#x7D22;&#x5F15;&#x503C;</span>

    <span class="hljs-keyword">return</span> i
</code></pre>
<hr>
<h4 id="2&#x6316;&#x5751;&#x6CD5;&#xFF1A;-&#x5751;&#x5C31;&#x662F;-&#x57FA;&#x51C6;&#x6570;-&#x7684;&#x4F4D;&#x7F6E;&#x3002;">2.&#x6316;&#x5751;&#x6CD5;&#xFF1A; &#x5751;&#x5C31;&#x662F; &#x57FA;&#x51C6;&#x6570; &#x7684;&#x4F4D;&#x7F6E;&#x3002;</h4>
<p>&#x6211;&#x4EEC;&#x6765;&#x505A;&#x4E2A;&#x8BE6;&#x89E3;&#xFF1A;</p>
<p>&#x6392;&#x5E8F; &#x4ECE;&#x5C0F;&#x5230;&#x5927;</p>
<p><img src="images/1.png" alt=""></p>
<p>&#x9996;&#x5148;&#xFF0C;&#x6211;&#x4EEC;&#x9009;&#x5B9A;&#x57FA;&#x51C6;&#x5143;&#x7D20;Pivot&#xFF0C;&#x5E76;&#x8BB0;&#x4F4F;&#x8FD9;&#x4E2A;&#x4F4D;&#x7F6E;index&#xFF0C;&#x8FD9;&#x4E2A;&#x4F4D;&#x7F6E;&#x76F8;&#x5F53;&#x4E8E;&#x4E00;&#x4E2A;&#x201C;&#x5751;&#x201D;&#x3002;&#x5E76;&#x4E14;&#x8BBE;&#x7F6E;&#x4E24;&#x4E2A;&#x6307;&#x9488;left&#x548C;right&#xFF0C;&#x6307;&#x5411;&#x6570;&#x5217;&#x7684;&#x6700;&#x5DE6;&#x548C;&#x6700;&#x53F3;&#x4E24;&#x4E2A;&#x5143;&#x7D20;&#x3002;</p>
<p><img src="images/2.png" alt=""></p>
<p>&#x63A5;&#x4E0B;&#x6765;&#xFF0C;&#x4ECE;right&#x6307;&#x9488;&#x5F00;&#x59CB;&#xFF0C;&#x628A;&#x6307;&#x9488;&#x6240;&#x6307;&#x5411;&#x7684;&#x5143;&#x7D20;&#x548C;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#x505A;&#x6BD4;&#x8F83;&#x3002;&#x5982;&#x679C;&#x6BD4;pivot&#x5927;&#xFF0C;&#x5219;right&#x6307;&#x9488;&#x5411;&#x5DE6;&#x79FB;&#x52A8;&#xFF1B;&#x5982;&#x679C;&#x6BD4;pivot&#x5C0F;&#xFF0C;&#x5219;&#x628A;right&#x6240;&#x6307;&#x5411;&#x7684;&#x5143;&#x7D20;&#x586B;&#x5165;&#x5751;&#x4E2D;&#x3002;</p>
<p>&#x5728;&#x5F53;&#x524D;&#x6570;&#x5217;&#x4E2D;&#xFF0C;1&lt;4&#xFF0C;&#x6240;&#x4EE5;&#x628A;1&#x586B;&#x5165;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#x6240;&#x5728;&#x4F4D;&#x7F6E;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;&#x5751;&#x7684;&#x4F4D;&#x7F6E;&#x3002;&#x8FD9;&#x65F6;&#x5019;&#xFF0C;&#x5143;&#x7D20;1&#x672C;&#x6765;&#x6240;&#x5728;&#x7684;&#x4F4D;&#x7F6E;&#x6210;&#x4E3A;&#x4E86;&#x65B0;&#x7684;&#x5751;&#x3002;&#x540C;&#x65F6;&#xFF0C;left&#x5411;&#x53F3;&#x79FB;&#x52A8;&#x4E00;&#x4F4D;</p>
<p><img src="images/3.png" alt=""></p>
<h5 id="&#x6B64;&#x65F6;&#xFF0C;left&#x5DE6;&#x8FB9;&#x7EFF;&#x8272;&#x7684;&#x533A;&#x57DF;&#x4EE3;&#x8868;&#x7740;&#x5C0F;&#x4E8E;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#x7684;&#x533A;&#x57DF;&#x3002;">&#x6B64;&#x65F6;&#xFF0C;left&#x5DE6;&#x8FB9;&#x7EFF;&#x8272;&#x7684;&#x533A;&#x57DF;&#x4EE3;&#x8868;&#x7740;&#x5C0F;&#x4E8E;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#x7684;&#x533A;&#x57DF;&#x3002;</h5>
<p>&#x63A5;&#x4E0B;&#x6765;&#xFF0C;&#x6211;&#x4EEC;&#x5207;&#x6362;&#x5230;left&#x6307;&#x9488;&#x8FDB;&#x884C;&#x6BD4;&#x8F83;&#x3002;&#x5982;&#x679C;left&#x6307;&#x5411;&#x7684;&#x5143;&#x7D20;&#x5C0F;&#x4E8E;pivot&#xFF0C;&#x5219;left&#x6307;&#x9488;&#x5411;&#x53F3;&#x79FB;&#x52A8;&#xFF1B;&#x5982;&#x679C;&#x5143;&#x7D20;&#x5927;&#x4E8E;pivot&#xFF0C;&#x5219;&#x628A;left&#x6307;&#x5411;&#x7684;&#x5143;&#x7D20;&#x586B;&#x5165;&#x5751;&#x4E2D;&#x3002;</p>
<p>&#x5728;&#x5F53;&#x524D;&#x6570;&#x5217;&#x4E2D;&#xFF0C;7&gt;4&#xFF0C;&#x6240;&#x4EE5;&#x628A;7&#x586B;&#x5165;index&#x7684;&#x4F4D;&#x7F6E;&#x3002;&#x8FD9;&#x65F6;&#x5019;&#x5143;&#x7D20;7&#x672C;&#x6765;&#x7684;&#x4F4D;&#x7F6E;&#x6210;&#x4E3A;&#x4E86;&#x65B0;&#x7684;&#x5751;&#x3002;&#x540C;&#x65F6;&#xFF0C;right&#x5411;&#x5DE6;&#x79FB;&#x52A8;&#x4E00;&#x4F4D;&#x3002;</p>
<p><img src="images/4.png" alt=""></p>
<h5 id="&#x6B64;&#x65F6;&#xFF0C;right&#x53F3;&#x8FB9;&#x6A59;&#x8272;&#x7684;&#x533A;&#x57DF;&#x4EE3;&#x8868;&#x7740;&#x5927;&#x4E8E;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#x7684;&#x533A;&#x57DF;&#x3002;">&#x6B64;&#x65F6;&#xFF0C;right&#x53F3;&#x8FB9;&#x6A59;&#x8272;&#x7684;&#x533A;&#x57DF;&#x4EE3;&#x8868;&#x7740;&#x5927;&#x4E8E;&#x57FA;&#x51C6;&#x5143;&#x7D20;&#x7684;&#x533A;&#x57DF;&#x3002;</h5>
<p>&#x4E0B;&#x9762;&#x6309;&#x7167;&#x521A;&#x624D;&#x7684;&#x601D;&#x8DEF;&#x7EE7;&#x7EED;&#x6392;&#x5E8F;&#xFF1A;</p>
<p>8&gt;4&#xFF0C;&#x5143;&#x7D20;&#x4F4D;&#x7F6E;&#x4E0D;&#x53D8;&#xFF0C;right&#x5DE6;&#x79FB;</p>
<p><img src="images/5.png" alt=""></p>
<p>2&lt;4&#xFF0C;&#x7528;2&#x6765;&#x586B;&#x5751;&#xFF0C;left&#x53F3;&#x79FB;&#xFF0C;&#x5207;&#x6362;&#x5230;left&#x3002;</p>
<p><img src="images/7.png" alt=""></p>
<p>6&gt;4&#xFF0C;&#x7528;6&#x6765;&#x586B;&#x5751;&#xFF0C;right&#x5DE6;&#x79FB;&#xFF0C;&#x5207;&#x6362;&#x5230;right&#x3002;</p>
<p><img src="images/6.png" alt=""></p>
<p>3&lt;4&#xFF0C;&#x7528;3&#x6765;&#x586B;&#x5751;&#xFF0C;left&#x53F3;&#x79FB;&#xFF0C;&#x5207;&#x6362;&#x5230;left&#x3002;</p>
<p><img src="images/8.png" alt=""></p>
<p>5&gt;4&#xFF0C;&#x7528;5&#x6765;&#x586B;&#x5751;&#xFF0C;right&#x53F3;&#x79FB;&#x3002;&#x8FD9;&#x65F6;&#x5019;left&#x548C;right&#x91CD;&#x5408;&#x5728;&#x4E86;&#x540C;&#x4E00;&#x4F4D;&#x7F6E;&#x3002;</p>
<p><img src="images/9.png" alt=""></p>
<p>&#x8FD9;&#x65F6;&#x5019;&#xFF0C;&#x628A;&#x4E4B;&#x524D;&#x7684;pivot&#x5143;&#x7D20;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;4&#x653E;&#x5230;index&#x7684;&#x4F4D;&#x7F6E;&#x3002;&#x6B64;&#x65F6;&#x6570;&#x5217;&#x5DE6;&#x8FB9;&#x7684;&#x5143;&#x7D20;&#x90FD;&#x5C0F;&#x4E8E;4&#xFF0C;&#x6570;&#x5217;&#x53F3;&#x8FB9;&#x7684;&#x5143;&#x7D20;&#x90FD;&#x5927;&#x4E8E;4&#xFF0C;&#x8FD9;&#x4E00;&#x8F6E;&#x4EA4;&#x6362;&#x7EC8;&#x544A;&#x7ED3;&#x675F;&#x3002;</p>
<p><img src="images/10.png" alt=""></p>
<p>&#x4E00;&#x4E0B;&#x5C31;&#x662F;&#x6316;&#x5751;&#x6CD5;&#x7684;&#x4EE3;&#x7801;&#x7684;&#x5B9E;&#x73B0;&#x3002;&#x5982;&#x679C;&#x6BD4;&#x57FA;&#x51C6;&#x6570;&#x5927;&#x90A3;&#x4E48;&#x5C31;&#x4E0D;&#x7528;&#x79FB;&#x52A8;&#x4F4D;&#x7F6E;&#xFF0C;&#xFF0C;&#x5982;&#x679C;&#x6BD4;&#x57FA;&#x51C6;&#x6570;&#x5C0F;&#x90A3;&#x4E48;&#x5C31;&#x53BB;&#x57FA;&#x51C6;&#x6570;&#x540E;&#x9762;&#x7684;&#x5751;&#x7684;&#x4F4D;&#x7F6E;&#x3002;</p>
<pre><code class="lang-python">
<span class="hljs-comment"># &#x300A;&#x7B97;&#x6CD5;&#x5BFC;&#x8BBA;&#x300B;&#x4E2D;&#x7684;&#x5FEB;&#x6392;&#x7A0B;&#x5E8F;</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">partition2</span><span class="hljs-params">(array,leftIndex,rightIndex)</span>:</span>
    <span class="hljs-comment">#&#x8BBE;&#x7F6E;&#x4E00;&#x4E2A; &#x5DE6;&#x8FB9;&#x7684;&#x6307;&#x9488;&#x4F4D;&#x7F6E; &#x4E3A; &#x5DE6;&#x4FA7;&#x7684; &#x524D;&#x4E00;&#x4E2A;</span>
    i = leftIndex -<span class="hljs-number">1</span>
    <span class="hljs-comment">#&#x904D;&#x5386; &#x9664; &#x57FA;&#x51C6;&#x6570;&#x4E4B;&#x5916;&#x7684; &#x6570;</span>
    <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(leftIndex,rightIndex):
        <span class="hljs-comment">#&#x6BD4;&#x8F83; &#x904D;&#x5386;&#x7684;&#x6570; &#x548C; &#x57FA;&#x51C6;&#x6570; &#xFF0C;&#x82E5;&#x662F;&#x5C0F;&#x4E8E;&#x57FA;&#x51C6;&#x6570; &#x5219; &#x6362;&#x5230;&#x6570;&#x7EC4;&#x524D;&#x9762;&#x53BB;</span>
        <span class="hljs-keyword">if</span> array[j] &lt; array[rightIndex]:
            <span class="hljs-comment">#&#x4EA4;&#x6362;&#x4F4D;&#x7F6E;&#xFF0C;&#x5C06;&#x904D;&#x5386;&#x7684;&#x6BD4; &#x57FA;&#x51C6;&#x6570;&#x5C0F;&#x7684;&#x6570; &#x653E;&#x5230; &#x6211;&#x4EEC;&#x6307;&#x9488; &#x7684; &#x540E;&#x4E00;&#x4E2A;&#x4E0A;&#xFF0C;&#x7136;&#x540E; &#x8FD9;&#x4E2A;&#x65F6;&#x5019;&#x6307;&#x9488;&#x5411;&#x540E;&#x79FB;&#x4E00;&#x4F4D;&#x3002;&#x5F53;&#x904D;&#x5386;&#x7684;&#x6570;&#x5927;&#x4E8E;&#x6211;&#x4EEC;&#x7684;&#x57FA;&#x51C6;&#x6570;&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x4E0D;&#x79FB;&#x52A8;&#xFF0C;&#x800C;&#x4E14; &#x6307;&#x9488;&#x4E5F;&#x4E0D;&#x53D1;&#x751F;&#x53D8;&#x5316;&#xFF0C;&#x90A3;&#x4E48; &#x5F53;&#x6211;&#x4EEC;&#x904D;&#x5386;&#x5B8C;&#x4E00;&#x5708;&#x4EE5;&#x540E;&#xFF0C;&#x628A; &#x6211;&#x4EEC;&#x7684;&#x57FA;&#x51C6;&#x6570; &#x653E;&#x5230; &#x7D22;&#x5F15;i &#x7684;&#x540E;&#x4E00;&#x4E2A; &#x4F4D;&#x7F6E;&#xFF0C;&#x90A3;&#x4E48;&#x5C31;&#x5F62;&#x6210;&#x4E86; &#x4E00;&#x4E2A; &#x57FA;&#x51C6;&#x6570; &#x5DE6;&#x8FB9;&#x90FD;&#x662F;&#x6BD4;&#x5B83;&#x5C0F;&#x7684;&#x6570;&#xFF0C;&#x57FA;&#x51C6;&#x6570;&#x53F3;&#x8FB9; &#x90FD;&#x662F;&#x6BD4;&#x5B83;&#x5927;&#x7684;&#x6570; &#x8FD9;&#x6837;&#x7684;&#x6A21;&#x5F0F;&#x3002;&#x7136;&#x540E;&#x8981;&#x628A; &#x7D22;&#x5F15; i &#x7684;&#x540E;&#x4E00;&#x4E2A;&#x4F4D;&#x7F6E; &#x4F5C;&#x4E3A;&#x57FA;&#x51C6;&#x6570; &#x4E0E; &#x539F;&#x57FA;&#x51C6;&#x6570; &#x4EA4;&#x6362;&#x4F4D;&#x7F6E;&#xFF0C;&#x8FDB;&#x800C;&#x53EF;&#x4EE5;&#x7B2C;&#x4E8C;&#x6B21;&#x6765; &#x904D;&#x5386;&#x6BD4;&#x8F83;&#x3002;</span>
            array[j],array[i+<span class="hljs-number">1</span>] = array[i+<span class="hljs-number">1</span>],array[j]
            i += <span class="hljs-number">1</span>
    <span class="hljs-comment">#&#x904D;&#x5386;&#x5B8C;&#x4E86;&#x4EE5;&#x540E;&#xFF0C;&#x5C06; left &#x4F4D;&#x7F6E;&#x4E0A;&#x7684;&#x6570; &#x548C; &#x6700;&#x540E;&#x4E00;&#x4E2A; &#x6570;  &#x5373; right &#x4E0A;&#x7684;&#x6570;&#x4E92;&#x6362;&#x4F4D;&#x7F6E;&#xFF0C;&#x5C31; &#x91CD;&#x7F6E; &#x57FA;&#x51C6;&#x6570;&#x4E86;&#x3002;</span>
    array[rightIndex],array[i+<span class="hljs-number">1</span>] = array[i+<span class="hljs-number">1</span>],array[rightIndex]
    <span class="hljs-comment">#&#x8FD4;&#x56DE;&#x57FA;&#x51C6;&#x7684;&#x4E0B;&#x6807;</span>
    <span class="hljs-keyword">return</span> i+<span class="hljs-number">1</span>
</code></pre>

                    
                    </section>
                
                
                </div>
            </div>
        </div>

        
        <a href="../六大排序/六大基本排序.html" class="navigation navigation-prev " aria-label="Previous page: 六大基本排序"><i class="fa fa-angle-left"></i></a>
        
        
        <a href="../算法的介绍/字典序算法.html" class="navigation navigation-next " aria-label="Next page: 字典序算法"><i class="fa fa-angle-right"></i></a>
        
    </div>
</div>

        
<script src="../gitbook/app.js"></script>

    
    <script src="../gitbook/plugins/gitbook-plugin-search/lunr.min.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-search/search.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-sharing/buttons.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-fontsettings/buttons.js"></script>
    

<script>
require(["gitbook"], function(gitbook) {
    var config = {"highlight":{},"search":{"maxIndexSize":1000000},"sharing":{"facebook":true,"twitter":true,"google":false,"weibo":false,"instapaper":false,"vk":false,"all":["facebook","google","twitter","weibo","instapaper"]},"fontsettings":{"theme":"white","family":"sans","size":2}};
    gitbook.start(config);
});
</script>

        
    </body>
    
</html>
